This invention relates to digital processors, and more particularly relates to methods for servicing multiple interrupts on a priority basis.
Priority based request arbitration systems determine the next request to be serviced, i.e., the xe2x80x9cwinner,xe2x80x9d based upon which request priority is highest, pending and enabled. Priority assignments are generally based on degrees of importance, in this case of requests. If multiple requests are programmed to the same priority, fairness protocols are used to determine the next winner. A mechanism is fair when any given request is not serviced twice until all pending requests are serviced once. Such arbitration systems are frequently used in digital processor interrupt servicing systems. In fact, throughout this document the term xe2x80x9crequestxe2x80x9d and xe2x80x9cinterruptxe2x80x9d are used synonymously (an interrupt is a request for service).
The simplest fairness protocol is system based and ensures that a request does not occur twice for a predetermined length of time. This type of fairness includes Rate Monotonic Scheduling Theory (Louis Sha from Carnegie Mellon University). However, for many systems, requests are not able to be deterministically scheduled a priori.
A second form of fairness protocol is xe2x80x9cFirst Come First Served (FCFS)xe2x80x9d (Udi Manber and Mary Vernon, University of Wisconsin). In this protocol, each time the source of the request loses, it increments a counter. The counter value is used as the least significant bits of the priority field to determine the next winner. When multiple requests are all of the same priority value the leftmost is selected as the winner. This mechanism is gate intensive and potentially slows the rate at which the next winner can be determined.
Another mechanism commonly used in busses like Futurebus+ is xe2x80x9cRound Robinxe2x80x9d (Udi Manber and Mary Vernon, University of Wisconsin). In this protocol, a module checks if it lost and the winner is to the left (arbitrarily but consistently ordered) of itself. If so, it sets a round robin bit which is used as the least significant bit of the priority value to determine the winner. When multiple requests are all of the same priority value the leftmost is selected as the winner. This mechanism is a vast improvement over First Come First Served by reducing the effect on the amount of storage needed to determine fairness and also to reduce the time required to determine the winner.
However, there is a need to further reduce the storage necessary, in most cases, and the time required to determine a winner in priority based request arbitration systems.
The present invention provides a snapshot arbiter system for servicing multiple interrupt requests for a central processing unit (CPU) in a digital processor system, and for providing interrupts to the CPU corresponding to the interrupt requests. The system includes a synchronizer adapted to synchronize interrupt requests to a clock as they are received, and an interrupt masker adapted to receive a set of indicators identifying interrupt requests to be masked and to output active indicators that are a set of active interrupt request values corresponding to received interrupt requests that are not masked. Also included is a priority encoder block adapted to receive a set of priority values for respective interrupt requests and to provide as an output priority indicators that are a set of codes representing the priority values. A snapshot enable block is included, adapted to store enable indictors that are a set of bits representing currently enabled interrupt requests, and output those bits as enable bits. Also included is a snapshot register adapted to receive the active indicators and the enable indicators, and to output snapshot indicators that are a set of values representing the currently active and enabled interrupts. An interrupt generation block is included, adapted to receive the snapshot indicators and the priority indicators, and to output an interrupt corresponding to a highest priority interrupt request, to output a highest indicator representing a highest interrupt Priority level in the snapshot register. and to output for reading by the CPU an identification indicator representing a currently selected interrupt request. Finally, an interrupt preemption block is included, adapted to receive the priority indicators. the active indicators and the highest indicator, and to output to the snapshot enable block a set of bits corresponding to each current interrupt request higher in priority than all of the interrupt requests represented in the snapshot register, for updating the snapshot enable block.
The present invention is equally applicable to any request/grant arbitration protocol.